﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using Sets = Algoritmia.DataStructures.Sets;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;

namespace Algoritmia.Problems.HamiltonianCycle.Reversible
{
    public class HamiltonianCycleStateSpace<TVertex> : IReversibleForwardStateSpace<HamiltonianCycleStateSpace<TVertex>.State, TVertex>
    {
        public class State
        {
            public readonly TVertex LastVertex;
            public readonly State Predecessor;
            public Sets.ISet<TVertex> Added { get; private set; }
            public readonly TVertex FirstVertex;

            private readonly Func<Sets.ISet<TVertex>> _createSet;

            public State(TVertex v,State predecessor = null, Func<Sets.ISet<TVertex>> createSet = null)
            {
                _createSet = createSet ?? (() => AlgoritmiaFactory.Sets<TVertex>.Default);
                LastVertex = v;
                Predecessor = predecessor;
                Added = predecessor == null ? _createSet() : predecessor.Added;
                Added.Add(LastVertex);
                FirstVertex = predecessor == null ? v : predecessor.FirstVertex;
            }
        }

        private readonly IDigraph<TVertex> _g;

        public HamiltonianCycleStateSpace(IDigraph<TVertex> G)
        {
            _g = G;
        }

        #region Implementation of IForwardStateSpace<IList<TVertex>,TVertex>

        public State Decide(State state, TVertex decision)
        {
             return new State(decision,state);
        }

        public IEnumerable<TVertex> Decisions(State state)
        {
            if (state.Added.Count < _g.V.Count )
            {
                foreach (var vertex in _g.Successors(state.LastVertex))
                {
                    if (!state.Added.Contains(vertex))
                    {
                        yield return vertex;
                    }
                }
            }
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_g.V.First()); }
        }

        public bool IsFinal(State state)
        {
            return _g.V.All(state.Added.Contains) &&
                   _g.E.Contains(new Tuple<TVertex, TVertex>(state.LastVertex, state.FirstVertex));
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<HamiltonianCycleStateSpace<TVertex>.State,TVertex>

        public State Undo(State state, TVertex decision)
        {
            state.Added.Remove(decision);
            return state.Predecessor;
        }

        #endregion
    }

    public class HamiltonianCycleSolver<T>
    {
        private readonly BacktrackingEnumerator<HamiltonianCycleStateSpace<T>.State, T, Lists.IList<T>> _enumerator;
        private readonly Func<Lists.IList<T>> _createList;

        public HamiltonianCycleSolver(Func<Lists.IList<T>> createList = null)
        {
            _createList = createList ?? (() => AlgoritmiaFactory.Lists<T>.Default);
            _enumerator = new BacktrackingEnumerator<HamiltonianCycleStateSpace<T>.State, T, Lists.IList<T>>((space, i, d, f) =>
            {
                var list = _createList();
                list.Add(i.FirstVertex);
                                                                                                                         
                foreach (var e in d)
                {
                    list.Add(e);
                }
                return list;
            });
        }

        public Lists.IList<T> Solve(IDigraph<T> graph)
        {
            var stateSpace = new HamiltonianCycleStateSpace<T>(graph);
            return _enumerator.First(stateSpace);
        }

        public IEnumerable<Lists.IList<T>> SolveAll(IDigraph<T> graph)
        {
            var stateSpace = new HamiltonianCycleStateSpace<T>(graph);
            return _enumerator.Enumerate(stateSpace);
        }

    }
}
